/*
 * @Author: liangwu liangwu.lxy@foxmail.com
 * @Description:
 */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <dlfcn.h>
#include <unistd.h>
#include <stdint.h>

typedef int (*pthread_mutex_lock_t)(pthread_mutex_t *mutex);
typedef int (*pthread_mutex_unlock_t)(pthread_mutex_t *mutex);

pthread_mutex_lock_t pthread_mutex_lock_f;
pthread_mutex_unlock_t pthread_mutex_unlock_f;



#define MAX	(1 << 10)

enum Type {
	PROCESS,
	RESOURCE
};

// 表示线程和获取的锁
struct source_type {
	uint64_t id;			// 资源标识 [线程id | lock addr]
	enum Type type;
	uint64_t lock_id;		// lock地址
	int degree;				// 等待获取锁的线程个数
};


struct vertex {
	struct source_type s;
	struct vertex *next;
};

struct task_graph {
	struct vertex list[MAX]; 	// <selfid, thid>
	int num;
	struct source_type locklist[MAX]; // 成功绑定的关系 <线程,锁>
	int lockidx;		// 代表<线程,锁>关系的个数

	pthread_mutex_t mutex;
};

struct task_graph *TaskGraph = NULL;
int path[MAX+1] = {0};	// 记录遍历过程中的路径
int visited[MAX] = {0};
int k = 0;
int deadlock = 0;


struct vertex *create_vertex(struct source_type type) {

	struct vertex *tex = (struct vertex *)calloc(1, sizeof(struct vertex ));
	if (tex == NULL) {
		return NULL;
	}

	tex->s = type;
	tex->next = NULL;

	return tex;

}

/*
*	@brief 在 list 中搜索对应的 type
* 	@return index of vertex_list
*/
int search_vertex(struct source_type type) {

	int i = 0;

	for (i = 0;i < TaskGraph->num;i ++) {

		if (TaskGraph->list[i].s.type == type.type && TaskGraph->list[i].s.id == type.id) {
			return i;
		}

	}

	return -1;
}

/*
*	@brief 在 vertex-list 不存在此资源将添加新的 vertex
*/
void add_vertex(struct source_type type) {

	if (search_vertex(type) == -1) {

		TaskGraph->list[TaskGraph->num].s = type;
		TaskGraph->list[TaskGraph->num].next = NULL;
		TaskGraph->num ++;

	}

}

/*
* 	@brief 源点指向目的顶点
*/
int add_edge(struct source_type from, struct source_type to) {

	add_vertex(from);
	add_vertex(to);

	struct vertex *v = &(TaskGraph->list[search_vertex(from)]);

	while (v->next != NULL) {
		v = v->next;
	}

	v->next = create_vertex(to);

}

/*
*	@brief 检验是否存在节点i 指向 节点j 的边
*/
int verify_edge(struct source_type i, struct source_type j) {

	if (TaskGraph->num == 0) return 0;

	int idx = search_vertex(i);
	if (idx == -1) {
		return 0;
	}

	struct vertex *v = &(TaskGraph->list[idx]);

	while (v != NULL) {

		if (v->s.id == j.id) return 1;

		v = v->next;

	}

	return 0;

}


int remove_edge(struct source_type from, struct source_type to) {

	int idxi = search_vertex(from);
	int idxj = search_vertex(to);

	if (idxi != -1 && idxj != -1) {

		struct vertex *v = &TaskGraph->list[idxi];
		struct vertex *remove;

		while (v->next != NULL) {

			if (v->next->s.id == to.id) {

				remove = v->next;
				v->next = v->next->next;

				free(remove);
				break;

			}

			v = v->next;
		}

	}

}


void print_deadlock(void) {

	int i = 0;

	printf("deadlock : ");
	for (i = 0;i < k-1;i ++) {

		printf("%ld --> ", TaskGraph->list[path[i]].s.id);

	}

	printf("%ld\n", TaskGraph->list[path[i]].s.id);

}


/*
*	@brief 从指定的节点开始遍历，
*/
int DFS(int idx) {

	struct vertex *ver = &TaskGraph->list[idx];
	if (visited[idx] == 1) {

		path[k++] = idx;
		print_deadlock();
		deadlock = 1;

		return 0;
	}

	visited[idx] = 1;
	path[k++] = idx;

	while (ver->next != NULL) {

		DFS(search_vertex(ver->next->s));
		k --;

		ver = ver->next;

	}


	return 1;

}


/*
*	@brief 初始化 visited 和 path，调用 DFS
*/
void search_for_cycle(int idx) {

	struct vertex *ver = &TaskGraph->list[idx];
	visited[idx] = 1;
	k = 0;
	path[k++] = idx;

	while (ver->next != NULL) {

		int i = 0;
		for (i = 0;i < TaskGraph->num;i ++) {
			if (i == idx) continue;

			visited[i] = 0;
		}

		for (i = 1;i <= MAX;i ++) {
			path[i] = -1;
		}
		k = 1;

		DFS(search_vertex(ver->next->s));
		ver = ver->next;
	}

}


void check_dead_lock(void) {

	int i = 0;

	deadlock = 0;
	for (i = 0;i < TaskGraph->num;i ++) {
		if (deadlock == 1) break;
		search_for_cycle(i);
	}

	if (deadlock == 0) {
		printf("no deadlock\n");
	}

}


// 死锁检测线程例行函数
static void *thread_routine(void *args) {

	while (1) {

		sleep(5);
		check_dead_lock();

	}

}

void start_check(void) {

	TaskGraph = (struct task_graph*)malloc(sizeof(struct task_graph));
	TaskGraph->num = 0;
	TaskGraph->lockidx = 0;

	pthread_t tid;

	pthread_create(&tid, NULL, thread_routine, NULL);

}


/*
*	@brief 在 lock_list 搜索lock
*/
int search_lock(uint64_t lock) {

	int i = 0;

	for (i = 0;i < TaskGraph->lockidx;i ++) {

		if (TaskGraph->locklist[i].lock_id == lock) {
			return i;
		}
	}

	return -1;
}

/*
*	@return 在 lock_list 的空闲索引
*/
int search_empty_lock(uint64_t lock) {

	int i = 0;

	for (i = 0;i < TaskGraph->lockidx;i ++) {

		if (TaskGraph->locklist[i].lock_id == 0) {
			return i;
		}
	}

	return TaskGraph->lockidx;

}


int inc(int *value, int add) {

	int old;

	__asm__ volatile(
		"lock;xaddl %2, %1;"
		: "=a"(old)
		: "m"(*value), "a" (add)
		: "cc", "memory"
	);

	return old;
}


void print_locklist(void) {

	int i = 0;

	printf("print_locklist: \n");
	printf("---------------------\n");
	for (i = 0;i < TaskGraph->lockidx;i ++) {
		printf("threadid : %ld, lockid: %ld\n", TaskGraph->locklist[i].id, TaskGraph->locklist[i].lock_id);
	}
	printf("---------------------\n\n\n");
}


/*
*	@brief 建立以线程id为源顶点指向lockadrr所属顶点的有向边
*/
void lock_before(uint64_t thread_id, uint64_t lockaddr) {


	int idx = 0;
	// list<threadid, toThreadid>

	for(idx = 0;idx < TaskGraph->lockidx;idx ++) {
		if (TaskGraph->locklist[idx].lock_id == lockaddr) {

			struct source_type from;
			from.id = thread_id;
			from.type = PROCESS;
			add_vertex(from);

			struct source_type to;
			to.id = TaskGraph->locklist[idx].id;
			TaskGraph->locklist[idx].degree++;
			to.type = PROCESS;
			add_vertex(to);

			if (!verify_edge(from, to)) {
				add_edge(from, to); //
			}

		}
	}
}


/*
*	@brief 	表示锁获取成功，若不存在<线程,锁>关系则创建，
* 			若存在关系则断开以线程id为源顶点指向lockadrr所属顶点的有向边
*/
void lock_after(uint64_t thread_id, uint64_t lockaddr) {

	int idx = 0;
	if (-1 == (idx = search_lock(lockaddr))) {  // lock list opera

		int eidx = search_empty_lock(lockaddr);

		TaskGraph->locklist[eidx].id = thread_id;
		TaskGraph->locklist[eidx].lock_id = lockaddr;

		inc(&TaskGraph->lockidx, 1);

	} else {


		struct source_type from;
		from.id = thread_id;
		from.type = PROCESS;

		struct source_type to;
		to.id = TaskGraph->locklist[idx].id;
		TaskGraph->locklist[idx].degree --;
		to.type = PROCESS;

		if (verify_edge(from, to))
			remove_edge(from, to);

		// 更改锁的所属关系
		TaskGraph->locklist[idx].id = thread_id;

	}

}


void unlock_after(uint64_t thread_id, uint64_t lockaddr) {


	int idx = search_lock(lockaddr);

	if (TaskGraph->locklist[idx].degree == 0) {
		TaskGraph->locklist[idx].id = 0;
		TaskGraph->locklist[idx].lock_id = 0;
		//inc(&TaskGraph->lockidx, -1);
	}

}


int pthread_mutex_lock(pthread_mutex_t *mutex) {
	pthread_t selfid = pthread_self(); //
	printf("thread id:%ld lock_before \n", selfid);
	lock_before(selfid, (uint64_t)mutex);
    pthread_mutex_lock_f(mutex);
	printf("thread id:%ld lock_after\n", selfid);
	lock_after(selfid, (uint64_t)mutex);
	return 0;
}


int pthread_mutex_unlock(pthread_mutex_t *mutex) {
	pthread_t selfid = pthread_self();

    pthread_mutex_unlock_f(mutex);
	printf("thread id:%ld unlock_after\n", selfid);
	unlock_after(selfid, (uint64_t)mutex);
	return 0;
}

static int init_hook() {
	pthread_mutex_lock_f = dlsym(RTLD_NEXT, "pthread_mutex_lock");
	pthread_mutex_unlock_f = dlsym(RTLD_NEXT, "pthread_mutex_unlock");

	return 0;
}




#ifdef __DEBUG

pthread_mutex_t mutex_1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_3 = PTHREAD_MUTEX_INITIALIZER;

static void* thread_routine_a(void *arg) {
	printf("thread_routin_a enter\n");
	pthread_mutex_lock(&mutex_1);
	sleep(1);
	pthread_mutex_lock(&mutex_2);
	pthread_mutex_lock(&mutex_3);
	pthread_mutex_unlock(&mutex_3);
	pthread_mutex_unlock(&mutex_2);
	pthread_mutex_unlock(&mutex_1);
	return NULL;
}


static void* thread_routine_b(void *arg) {
	printf("thread_routin_b enter\n");
	pthread_mutex_lock(&mutex_2);
	sleep(1);
	pthread_mutex_lock(&mutex_3);
	pthread_mutex_lock(&mutex_1);
	pthread_mutex_unlock(&mutex_1);
	pthread_mutex_unlock(&mutex_3);
	pthread_mutex_unlock(&mutex_2);
	return NULL;
}


static void* thread_routine_c(void *arg) {
	printf("thread_routin_c enter\n");
	pthread_mutex_lock(&mutex_3);
	sleep(1);
	pthread_mutex_lock(&mutex_2);
	pthread_mutex_lock(&mutex_1);
	pthread_mutex_unlock(&mutex_1);
	pthread_mutex_unlock(&mutex_2);
	pthread_mutex_unlock(&mutex_3);
	return NULL;
}


int main(void) {
	init_hook();
	pthread_t pidlist[3];
	start_check();
	printf("start_check\n");
	pthread_create(&pidlist[0], NULL, thread_routine_a, NULL);
	pthread_create(&pidlist[1], NULL, thread_routine_b, NULL);
	pthread_create(&pidlist[2], NULL, thread_routine_c, NULL);

	sleep(10);
	int i;
	for (i=0; i<3; i++) {
		pthread_join(pidlist[i], NULL);
	}

	return 0;
}


#endif // !__DEBUG